class LRUCache {
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {}
    
    int get(int key) {
        auto ret=_hashMap.find(key);
        if(ret!=_hashMap.end())
        {
            LtIter it=ret->second;

            _LRUList.splice(_LRUList.begin(),_LRUList,it);

            return it->second;
        }
        else
        {
            return -1;
        }
    }
    
    void put(int key, int value) {
        auto ret=_hashMap.find(key);
        if(ret==_hashMap.end())
        {
            //满了，先删除数据
            if(_capacity==_hashMap.size())
            {
                pair<int,int> back=_LRUList.back();
                _hashMap.erase(back.first);
                _LRUList.pop_back();
            }

            _LRUList.push_front(make_pair(key,value));
            _hashMap[key]=_LRUList.begin();
        }
        else{
            LtIter it=ret->second;
            it->second=value;

            _LRUList.splice(_LRUList.begin(),_LRUList,it);
        }
    }
private:
    typedef list<pair<int,int>>::iterator LtIter;
    unordered_map<int,LtIter> _hashMap;

    list<pair<int,int>> _LRUList;

    size_t _capacity;
};
